package 代码随想录_补充题目;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author zx
 * @create 2023-02-08 21:02
 */
public class 有多少小于当前数字的数字_1365 {
    /**
     * 排序+HashMap, 分为三步：
     * 1.将数组由小到大排列；
     * 2.利用HashMap记录每一个数字所在数组的位置，即有多少个小于它的数
     * 3.将HashMap的值写入答案数组
     * @param nums
     * @return
     */
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] temp = new int[nums.length];
        //使用数组temp将数组nums由小到大排列
        for(int i = 0;i < nums.length;i++){
            temp[i] = nums[i];
        }
        Arrays.sort(temp);
        //利用HashMap记录temp[i]所在的位置，即有多少个小于它的数
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = temp.length - 1;i >= 0;i--){
            map.put(temp[i],i);
        }
        int[] res = new int[nums.length];
        //写入答案
        for(int i = 0;i < nums.length;i++){
            res[i] = map.get(nums[i]);
        }
        return res;
    }

    public int[] smallerNumbersThanCurrent2(int[] nums) {
        int[] temp = new int[nums.length];
        //使用数组temp将数组nums由小到大排列
        for(int i = 0;i < nums.length;i++){
            temp[i] = nums[i];
        }
        Arrays.sort(temp);
        //利用HashMap记录temp[i]所在的位置，即有多少个小于它的数
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < temp.length; i++) {
            //遇到了相同的数字，那么不需要更新该number的情况
            if (!map.containsKey(temp[i])) {
                map.put(temp[i], i);
            }
        }
        int[] res = new int[nums.length];
        //写入答案
        for(int i = 0;i < nums.length;i++){
            res[i] = map.get(nums[i]);
        }
        return res;
    }
}
